class Solution {
    /*
        思路1：相当于并查集，维护一个[L,R]区间（L最左边，R最右边），
        判断遍历元素能否加入到这个区间，如果能加入并更新R边界即可
        （注意，遍历需要保证数组按L有序即可）
    */
    public static int[][] merge(int[][] intervals) {
        // 排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });

        List<Node> ans = new ArrayList<>();
        int i = 0;
        while (i < intervals.length) {
            Node maxNode = new Node(intervals[i][0], intervals[i][1]);
            while (i + 1 < intervals.length && intervals[i + 1][0] <= maxNode.r) {
                maxNode.r = Math.max(maxNode.r, intervals[i + 1][1]);
                i++;
            }
            i++;
            ans.add(maxNode);
        }
        int[][] res = new int[ans.size()][];
        for (int j = 0; j < ans.size(); j++) {
            res[j] = new int[]{ans.get(j).l, ans.get(j).r};
        }
        return res;
    }

    static class Node {
        int l, r;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
}
class Solution {
    /*
        思路2：判断两个区间是否相交，如果相交就合并
    */
    public int[][] merge(int[][] intervals) {
        // 排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });

        List<int[]> ans = new ArrayList<>();
        for (int[] item : intervals) {
            // 如果两个区间相交，那么就合并区间
            if( ans.size()>0 &&  ans.get(ans.size()-1)[1]>=item[0] ){
                ans.get(ans.size()-1)[1] = Math.max(item[1],ans.get(ans.size()-1)[1]);
            }
            else{
                ans.add(item);
            }
        };
        return ans.toArray(new int[ans.size()][]);
    }
}